# 本质上升序列(好题)
# Date: 2025/03/27

def count_sec_seq(s: str):
    """感觉好像和某道题很像, 需要找找"""
    n = len(s)
    dp = [1] * n  # dp[i]表示以s[i]为结尾的子序列个数
    for i in range(n):
        for j in range(i):
            if s[i] > s[j]:
                dp[i] += dp[j]
            elif s[j] == s[i]:
                dp[i] -= dp[j]
    return sum(dp)


if __name__ == '__main__':
    print(count_sec_seq("abcde"))
    print(count_sec_seq("abcbe"))
    print(count_sec_seq("abcdab"))
    print(count_sec_seq("tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdaruf"
                        "mliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwou"
                        "lxbaeqkqhfwl"))
